Scroll Progress Bar

Binary Search

Binary search is an efficient search algorithm used to find a specific element in a sorted array. The algorithm repeatedly divides the array in half and checks if the middle element matches the target. If not, it narrows down the search to the left or right half of the array, and the process continues until the target element is found or the search space becomes empty.

Sample Code with Explanation and Output:

#include <stdio.h>

// Binary Search function
int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // Found the target at index mid
        } else if (arr[mid] < target) {
            left = mid + 1; // Target lies in the right half
        } else {
            right = mid - 1; // Target lies in the left half
        }
    }
    
    return -1; // Target not found
}

int main() {
    int sortedArray[] = {10, 20, 30, 40, 50, 60, 70};
    int n = sizeof(sortedArray) / sizeof(sortedArray[0]);
    int target = 40;

    int index = binarySearch(sortedArray, n, target);

    if (index != -1) {
        printf("Element %d found at index %d.\n", target, index);
    } else {
        printf("Element not found in the array.\n");
    }

    return 0;
}
Output:

Element 40 found at index 3.
Explanation:
  • In the sample code, define a binary search function binarySearch, which takes a sorted array arr, the size of the array n, and the target element target as input.
  • The function initializes two variables, left and right, representing the leftmost and rightmost indices of the search space, respectively.
  • Inside the while loop, calculate the mid index by taking the average of left and right. use this index to access the middle element of the array.
  • If the middle element is equal to the target, return the mid index, indicating that found the element.
  • If the middle element is less than the target, narrow the search to the right half by updating left to mid + 1.
  • If the middle element is greater than the target, narrow the search to the left half by updating right to mid - 1.
  • Repeat the process until left is less than or equal to right.
  • If the target is not found in the array, return -1.
  • In the main function, create a sorted array sortedArray containing integers {10, 20, 30, 40, 50, 60, 70} and specify the target element 40.
  • Call the binarySearch function to search for the target in the array.
  • The function returns the index 3, which indicates that the target 40 is found at index 3 in the array. print this information.
  • If the target re not found, the function would return -1, and would print "Element not found in the array."

What is binary search in C?

Search

What is the time complexity of binary search?

Logarithmic

What is the key requirement for binary search to work?

Sorted

What does binary search do to the search space in each step?

Halves

In binary search, what is checked to decide whether to search the left or right half of the array?

Middle